package it.storm.solution;

/**
 * 1583. 统计不开心的朋友
 * https://leetcode-cn.com/problems/count-unhappy-friends/
 */
public class Solutions_1583 {
    public static void main(String[] args) {
        int n = 4;
        int[][] preferences = {{1, 2, 3}, {3, 2, 0}, {3, 1, 0}, {1, 2, 0}};
        int[][] pairs = {{0, 1}, {2, 3}};  // output: 2

//        int n = 2;
//        int[][] preferences = {{1}, {0}};
//        int[][] pairs = {{1, 0}};  // output: 0

//        int n = 4;
//        int[][] preferences = {{1, 3, 2}, {2, 3, 0}, {1, 3, 0}, {0, 2, 1}};
//        int[][] pairs = {{1, 3}, {0, 2}};  // output: 4

        int result = unhappyFriends(n, preferences, pairs);
        System.out.println(result);
    }

    /**
     * 模拟法
     * 什么时候 x 会不开心呢？
     * 例：int[][] preferences = {{1, 2, 3}, {3, 2, 0}, {3, 1, 0}, {1, 2, 0}};
     *     int[][] pairs = {{0, 1}, {2, 3}};
     *
     *  1 的配对对象是 0，而 1 对 3，对 2 更亲近（因为 3 和 2 排在 0 的前面）-关注 preferences[1]
     *  那么对 2 和 3 进行判断，若其中 2 或 3 分别对 1 的亲近程度比各自的配对对象更高，那么 1 会不开心
     *  2 与 3 配对，2 对 3 的亲近程度比 2 对 1 要高，1 不会不开心
     *  3 与 2 配对，可是 3 对 1 的亲近程度却比 3 对 2 要高，1 就不开心了。
     */
    public static int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        int res = 0;
        // 记录下 n 个朋友，各自的配对对象，map[0] = 1：表示朋友 0 的配对对象是 1
        int[] map = new int[n];
        for (int[] pair : pairs) {
            // x 的配对对象是 y，那么 y 的配对对象也就是 x
            int x = pair[0];
            int y = pair[1];
            map[x] = y;
            map[y] = x;
        }

        for (int i = 0; i < n; i++) {
            // 检查朋友 i 是否不开心
            if (unHappy(preferences, map, i)) {
                res ++;
            }
        }
        return res;
    }

    public static boolean unHappy(int[][] preferences, int[] map, int me) {
        // pair（0） 是 me（1） 的配对对象
        int pair = map[me];

        // 获取到 me（1） 与各个朋友的亲近程度列表并进行遍历
        for (int friend : preferences[me]) {
            if (friend == pair) {
                // 两种情况：
                // 1.先遍历到 pair，说明 me 对 pair 的亲近程度很高
                // 2.遍历过了那些亲近程度高的朋友后，但是没有返回结果，说明那么朋友对自己配对对象
                // 的亲近程度也很高（起码比对 me 要高）
                return false;
            }
            // friend 不是 pair，则说明 me 对 friend 的亲近程度要比 pair 高
            // 需要检查 friend 有没有对 me 的亲近程度要高于自己的配对对象 friendPair
            // 如果检查？遍历 friendPref 数组，若 me 排在 friend 前面，则 me 会不开心

            // 获取到 friend（3） 的配对对象（2）
            int friendPair = map[friend];
            // 获取到 friend 对朋友们的亲近程度数组（{1, 2, 0}）
            int[] friendPref = preferences[friend];

            for (int p : friendPref) {
                if (p == me) {
                    // 先遍历到 me，说明 friend 对 me 更亲近，me 不开心
                    return true;
                } else if (p == friendPair) {
                    // 先遍历到 friend 的配对对象，说明 friend 对配对对象更亲近
                    break;
                }
            }
        }
        return false;
    }
}
